#ifndef SP_H_
#define SP_H_

#include <algorithm>
#include <array>
#include <queue>
#include <string>
#include <utility>
#include <vector>


namespace lxj
{
// Dijkstra算法模版（Leetcode）
// 网络延迟时间
// 有 n 个网络节点，标记为 1 到 n
// 给你一个列表 times，表示信号经过 有向 边的传递时间
// times[i] = (ui, vi, wi)，表示从ui到vi传递信号的时间是wi
// 现在，从某个节点 s 发出一个信号
// 需要多久才能使所有节点都收到信号
// 如果不能使所有节点收到信号，返回 -1
// 测试链接 : https://leetcode.cn/problems/network-delay-time
class DijkstraLeetcode {
    // 链式前向星
    inline static int              MAXN   = 101;
    inline static int              MAXM   = 6001;
    inline static std::vector<int> head   = std::vector<int>(MAXN);
    inline static std::vector<int> to     = std::vector<int>(MAXM);
    inline static std::vector<int> next   = std::vector<int>(MAXM);
    inline static std::vector<int> weight = std::vector<int>(MAXM);
    inline static int              cnt    = 0;

    // 反向索引堆
    inline static std::vector<int> heap = std::vector<int>(MAXN);

    // where[v] = -1，表示v这个节点，从来没有进入过堆
    // where[v] = -2，表示v这个节点，已经弹出过了
    // where[v] = i(>=0)，表示v这个节点，在堆上的i位置
    inline static std::vector<int> where    = std::vector<int>(MAXN);
    inline static int              heapSize = 0;

    inline static std::vector<int> distance = std::vector<int>(MAXN);

    inline void build(int n)
    {
        constexpr int MAX = ~(1 << 31);
        cnt               = 1;
        heapSize          = 0;
        std::fill(head.begin(), head.begin() + n + 1, 0);
        std::fill(where.begin(), where.begin() + n + 1, -1);
        std::fill(distance.begin(), distance.begin() + n + 1, MAX);
    }

    inline void addEdge(int u, int v, int w)
    {
        next[cnt]   = head[u];
        to[cnt]     = v;
        weight[cnt] = w;
        head[u]     = cnt++;
    }

    inline void addOrUpdateOrIgnore(int v, int c)
    {
        if (where[v] == -1) {
            heap[heapSize] = v;
            where[v]       = heapSize++;
            distance[v]    = c;
            heapInsert(where[v]);
        }
        else if (where[v] >= 0) {
            distance[v] = distance[v] < c ? distance[v] : c;
            heapInsert(where[v]);
        }
    }

    inline void heapInsert(int i)
    {
        while (distance[heap[i]] < distance[heap[(i - 1) / 2]]) {
            swap(i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    inline void heapify(int i)
    {
        int l = i * 2 + 1;
        while (l < heapSize) {
            int best = l + 1 < heapSize && distance[heap[l + 1]] < distance[heap[l]] ? l + 1 : l;
            best     = distance[heap[best]] < distance[heap[i]] ? best : i;
            if (best == i) break;
            swap(best, i);
            i = best;
            l = i * 2 + 1;
        }
    }

    inline void swap(int i, int j)
    {
        int tmp        = heap[i];
        heap[i]        = heap[j];
        heap[j]        = tmp;
        where[heap[i]] = i;
        where[heap[j]] = j;
    }

    inline bool isEmpty() { return heapSize == 0; }

    inline int pop()
    {
        int ans = heap[0];
        swap(0, --heapSize);
        heapify(0);
        where[ans] = -2;
        return ans;
    }

public:
    // 动态建图+普通堆的实现
    inline int networkDelayTime1(std::vector<std::vector<int>>& times, int n, int k)
    {
        std::vector<std::vector<std::pair<int, int>>> graph(n + 1);
        for (auto& t : times) {
            graph[t[0]].push_back({t[1], t[2]});
        }

        constexpr int    MAX = ~(1 << 31);
        std::vector<int> distance(n + 1, MAX);
        distance[k]   = 0;
        bool* visited = new bool[n + 1];
        std::fill(visited, visited + n + 1, false);

        auto my_comp = [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
            return a.second > b.second;
        };
        std::
            priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(my_comp)>
                heap(my_comp);
        heap.push({k, 0});

        while (!heap.empty()) {
            int u = heap.top().first;
            heap.pop();
            if (visited[u]) continue;
            visited[u] = true;
            for (auto& edge : graph[u]) {
                int v = edge.first;
                int w = edge.second;
                if (!visited[v] && distance[u] + w < distance[v]) {
                    distance[v] = distance[u] + w;
                    heap.push({v, distance[v]});
                }
            }
        }
        int ans = ~MAX;
        for (int i = 1; i <= n; i++) {
            if (distance[i] == MAX) return -1;
            ans = ans > distance[i] ? ans : distance[i];
        }
        return ans;
    }

    inline int networkDelayTime2(std::vector<std::vector<int>>& times, int n, int k)
    {
        build(n);
        for (auto& edge : times) {
            addEdge(edge[0], edge[1], edge[2]);
        }
        addOrUpdateOrIgnore(k, 0);
        while (!isEmpty()) {
            int u = pop();
            for (int ei = head[u]; ei > 0; ei = next[ei])
                addOrUpdateOrIgnore(to[ei], distance[u] + weight[ei]);
        }

        constexpr int MAX = ~(1 << 31);
        int           ans = ~MAX;
        for (int i = 1; i <= n; i++) {
            if (distance[i] == MAX) return -1;
            ans = ans > distance[i] ? ans : distance[i];
        }
        return ans;
    }
};

// 最小体力消耗路径
// 你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights
// 其中 heights[row][col] 表示格子 (row, col) 的高度
// 一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1)
// （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动
// 你想要找到耗费 体力 最小的一条路径
// 一条路径耗费的体力值是路径上，相邻格子之间高度差绝对值的最大值
// 请你返回从左上角走到右下角的最小 体力消耗值
// 测试链接 ：https://leetcode.cn/problems/path-with-minimum-effort/
inline int minimumEffortPath(std::vector<std::vector<int>>& heights)
{
    constexpr int                 MAX = ~(1 << 31);
    int                           n   = heights.size();
    int                           m   = heights[0].size();
    std::vector<std::vector<int>> distance(n, std::vector<int>(m));
    for (auto& dis : distance) {
        std::fill(dis.begin(), dis.end(), MAX);
    }
    distance[0][0] = 0;

    std::vector<std::vector<bool>> visited(n, std::vector<bool>(m, false));

    int move[] = {-1, 0, 1, 0, -1};
    struct node {
        int a, b, c;
    };
    auto comp = [](const auto& a, const auto& b) { return a.c > b.c; };
    std::priority_queue<node, std::vector<node>, decltype(comp)> heap(comp);
    heap.push({.a = 0, .b = 0, .c = 0});
    while (!heap.empty()) {
        auto& record = heap.top();
        int   x      = record.a;
        int   y      = record.b;
        int   w      = record.c;
        heap.pop();
        if (visited[x][y]) continue;
        if (x == n - 1 && y == m - 1) return w;
        visited[x][y] = true;
        for (int i = 0, nx, ny; i < 4; i++) {
            nx = x + move[i];
            ny = y + move[i + 1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
                int nc = std::max(w, std::abs(heights[x][y] - heights[nx][ny]));
                if (nc < distance[nx][ny]) {
                    distance[nx][ny] = nc;
                    heap.push({.a = nx, .b = ny, .c = nc});
                }
            }
        }
    }
    return -1;
}

// 水位上升的泳池中游泳
// 在一个 n x n 的整数矩阵 grid 中
// 每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度
// 当开始下雨时，在时间为 t 时，水池中的水位为 t
// 你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台
// 假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的
// 当然，在你游泳的时候你必须待在坐标方格里面。
// 你从坐标方格的左上平台 (0，0) 出发
// 返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间
// 测试链接 : https://leetcode.cn/problems/swim-in-rising-water/
inline int swimInWater(std::vector<std::vector<int>>& grid)
{
    constexpr int                 MAX = ~(1 << 31);
    int                           n   = grid.size();
    int                           m   = grid[0].size();
    std::vector<std::vector<int>> distance(n, std::vector<int>(m, MAX));
    distance[0][0] = grid[0][0];

    std::vector<std::vector<bool>> visited(n, std::vector<bool>(m, false));
    int                            move[] = {-1, 0, 1, 0, -1};
    struct node {
        int a, b, c;
    };
    auto comp = [](const node& a, const node& b) { return a.c > b.c; };
    std::priority_queue<node, std::vector<node>, decltype(comp)> heap(comp);
    heap.push({.a = 0, .b = 0, .c = grid[0][0]});
    while (!heap.empty()) {
        auto& record = heap.top();
        int   x      = record.a;
        int   y      = record.b;
        int   c      = record.c;
        heap.pop();
        if (visited[x][y]) continue;
        visited[x][y] = true;
        if (x == n - 1 && y == m - 1) return c;
        for (int i = 0, nx, ny; i < 4; i++) {
            nx = x + move[i];
            ny = y + move[i + 1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
                int nc = std::max(c, grid[nx][ny]);
                if (nc < distance[nx][ny]) {
                    distance[nx][ny] = nc;
                    heap.push({.a = nx, .b = ny, .c = nc});
                }
            }
        }
    }
    return -1;
}

// 获取所有钥匙的最短路径
// 给定一个二维网格 grid ，其中：
// '.' 代表一个空房间、'#' 代表一堵、'@' 是起点
// 小写字母代表钥匙、大写字母代表锁
// 从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间
// 不能在网格外面行走，也无法穿过一堵墙
// 如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。
// 假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，
// 字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母
// 换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁
// 另外，代表钥匙和锁的字母互为大小写并按字母顺序排列
// 返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。
// 测试链接：https://leetcode.cn/problems/shortest-path-to-get-all-keys
class ShortestPathToGetAllKeys {
    inline constexpr static int MAXN = 31;
    inline constexpr static int MAXM = 31;
    inline constexpr static int MAXK = 6;

    inline static int  move[]                              = {-1, 0, 1, 0, -1};
    inline static char grid[MAXN][MAXM]                    = {};
    inline static bool visited[MAXN][MAXM][1 << MAXK]      = {};
    inline static int  queue[MAXN * MAXM * (1 << MAXK)][3] = {};
    inline static int  l = 0, r = 0;
    inline static int  n = 0, m = 0, key = 0;

    inline void build(const std::vector<std::string>& g)
    {
        l = r = key = 0;
        n           = g.size();
        m           = g[0].size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) grid[i][j] = g[i][j];
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '@') {
                    queue[r][0]   = i;
                    queue[r][1]   = j;
                    queue[r++][2] = 0;
                }
                if (grid[i][j] >= 'a' && grid[i][j] <= 'f') {
                    key |= 1 << (grid[i][j] - 'a');
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int s = 0; s <= key; s++) visited[i][j][s] = false;
            }
        }
    }

public:
    inline int shortestPathAllKeys(std::vector<std::string>& g)
    {
        build(g);
        int level = 1;
        while (l < r) {
            for (int k = 0, size = r - l, x, y, s; k < size; k++) {
                x = queue[l][0];
                y = queue[l][1];
                s = queue[l++][2];
                for (int i = 0, nx, ny, ns; i < 4; i++) {
                    nx = x + move[i];
                    ny = y + move[i + 1];
                    ns = s;
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] == '#') continue;
                    if (grid[nx][ny] >= 'A' && grid[nx][ny] <= 'F' &&
                        ((ns & (1 << (grid[nx][ny] - 'A'))) == 0))
                        continue;
                    if (grid[nx][ny] >= 'a' && grid[nx][ny] <= 'f')
                        ns |= (1 << (grid[nx][ny] - 'a'));
                    if (ns == key) return level;
                    if (!visited[nx][ny][ns]) {
                        visited[nx][ny][ns] = true;
                        queue[r][0]         = nx;
                        queue[r][1]         = ny;
                        queue[r++][2]       = ns;
                    }
                }
            }
            level++;
        }
        return -1;
    }
};

// 电动车游城市
// 小明的电动车电量充满时可行驶距离为 cnt，每行驶 1 单位距离消耗 1 单位电量，且花费 1 单位时间
// 小明想选择电动车作为代步工具。地图上共有 N 个景点，景点编号为 0 ~ N-1
// 他将地图信息以 [城市 A 编号,城市 B 编号,两城市间距离] 格式整理在在二维数组 paths，
// 表示城市 A、B 间存在双向通路。
// 初始状态，电动车电量为 0。每个城市都设有充电桩，
// charge[i] 表示第 i 个城市每充 1 单位电量需要花费的单位时间。
// 请返回小明最少需要花费多少单位时间从起点城市 start 抵达终点城市 end
// 测试链接 : https://leetcode.cn/problems/DFPeFJ/
inline int electricCarPlan(
    std::vector<std::vector<int>>& paths, int cnt, int start, int end, std::vector<int>& charge)
{
    int                                           n = charge.size();
    std::vector<std::vector<std::pair<int, int>>> graph(n);
    for (auto& p : paths) {
        graph[p[0]].push_back({p[1], p[2]});
        graph[p[1]].push_back({p[0], p[2]});
    }

    std::vector<std::vector<int>> distance(n, std::vector<int>(cnt + 1));
    constexpr int                 MAX = ~(1 << 31);
    for (int i = 0; i < n; i++) {
        std::fill(distance[i].begin(), distance[i].end(), MAX);
    }
    distance[start][0] = 0;
    std::vector<std::vector<bool>> visited(n, std::vector<bool>(cnt + 1, false));

    struct node {
        int a, b, c;
    };
    auto comp = [](const node& a, const node& b) { return a.c > b.c; };
    std::priority_queue<node, std::vector<node>, decltype(comp)> heap(comp);
    heap.push({.a = start, .b = 0, .c = 0});
    while (!heap.empty()) {
        auto& record = heap.top();
        int   cur    = record.a;
        int   power  = record.b;
        int   cost   = record.c;
        heap.pop();
        if (visited[cur][power]) continue;
        if (cur == end) return cost;
        visited[cur][power] = true;
        if (power < cnt) {
            if (!visited[cur][power + 1] && charge[cur] + cost < distance[cur][power + 1]) {
                distance[cur][power + 1] = charge[cur] + cost;
                heap.push({.a = cur, .b = power + 1, .c = cost + charge[cur]});
            }
        }
        for (auto& edge : graph[cur]) {
            int nextCity  = edge.first;
            int restPower = power - edge.second;
            int nextCost  = cost + edge.second;
            if (restPower >= 0 && !visited[nextCity][restPower] &&
                nextCost < distance[nextCity][restPower]) {
                distance[nextCity][restPower] = nextCost;
                heap.push({.a = nextCity, .b = restPower, .c = nextCost});
            }
        }
    }
    return -1;
}

// 飞行路线（语言提供的堆）
// Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司
// 该航空公司一共在n个城市设有业务，设这些城市分别标记为0 ~ n−1
// 一共有m种航线，每种航线连接两个城市，并且航线有一定的价格
// Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机
// 航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机
// 那么 Alice 和 Bob 这次出行最少花费多少
// 测试链接 : https://www.luogu.com.cn/problem/P4568
class FlightPath1 {
    inline constexpr static int MAXN = 10001;
    inline constexpr static int MAXM = 2 * 50001;
    inline constexpr static int MAXK = 11;

    // 链式前向星
    inline static int head[MAXN]   = {};
    inline static int to[MAXM]     = {};
    inline static int next[MAXM]   = {};
    inline static int weight[MAXM] = {};
    inline static int cnt          = 0;

    inline static int  distance[MAXN][MAXK] = {};
    inline static bool visited[MAXN][MAXK]  = {};
    inline static int  n = 0, k = 0;

    inline void build()
    {
        constexpr int MAX = ~(1 << 31);
        cnt               = 1;
        for (int i = 0; i < n; i++) {
            head[i] = 0;
            for (int j = 0; j <= k; j++) {
                distance[i][j] = MAX;
                visited[i][j]  = false;
            }
        }
    }

    inline void addEdge(int u, int v, int w)
    {
        next[cnt]   = head[u];
        to[cnt]     = v;
        weight[cnt] = w;
        head[u]     = cnt++;
    }

public:
    inline int getMinPrice(
        int city, std::vector<std::array<int, 3>>& vec, int start, int end, int k_count)
    {
        n = city;
        k = k_count;
        build();
        for (auto& v : vec) {
            addEdge(v[0], v[1], v[2]);
            addEdge(v[1], v[0], v[2]);
        }

        distance[start][0] = 0;

        auto comp = [](const auto& a, const auto& b) { return a[2] > b[2]; };
        std::priority_queue<std::array<int, 3>, std::vector<std::array<int, 3>>, decltype(comp)>
            heap(comp);
        heap.push({start, 0, 0});
        while (!heap.empty()) {
            auto& record = heap.top();
            int   u      = record[0];
            int   use    = record[1];
            int   cost   = record[2];
            heap.pop();
            if (visited[u][use]) continue;
            visited[u][use] = true;
            if (u == end) return cost;

            for (int ei = head[u], v, w; ei > 0; ei = next[ei]) {
                v = to[ei];
                w = weight[ei];
                if (use < k && distance[v][use + 1] > distance[u][use]) {
                    distance[v][use + 1] = distance[u][use];
                    heap.push({v, use + 1, distance[v][use + 1]});
                }
                if (distance[v][use] > distance[u][use] + w) {
                    distance[v][use] = distance[u][use] + w;
                    heap.push({v, use, distance[v][use]});
                }
            }
        }
        return -1;
    }
};
class FlightPath2 {
    inline constexpr static int MAXN = 10001;
    inline constexpr static int MAXM = 2 * 50001;
    inline constexpr static int MAXK = 11;

    // 链式前向星
    inline static int head[MAXN]   = {};
    inline static int to[MAXM]     = {};
    inline static int next[MAXM]   = {};
    inline static int weight[MAXM] = {};
    inline static int cnt          = 0;

    inline static int  distance[MAXN][MAXK] = {};
    inline static bool visited[MAXN][MAXK]  = {};
    inline static int  n = 0, k = 0;

    // 用自己的堆
    inline static int heap[MAXM * MAXK][3] = {};
    inline static int heapSize             = 0;

    inline void build()
    {
        cnt               = 1;
        heapSize          = 0;
        constexpr int MAX = ~(1 << 31);
        for (int i = 0; i < n; i++) {
            head[i] = 0;
            for (int j = 0; j <= k; j++) {
                distance[i][j] = MAX;
                visited[i][j]  = false;
            }
        }
    }

    inline void addEdge(int u, int v, int w)
    {
        next[cnt]   = head[u];
        to[cnt]     = v;
        weight[cnt] = w;
        head[u]     = cnt++;
    }

    inline void push(int u, int t, int c)
    {
        heap[heapSize][0] = u;
        heap[heapSize][1] = t;
        heap[heapSize][2] = c;
        int i             = heapSize++;
        while (heap[i][2] < heap[(i - 1) / 2][2]) {
            swap(i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    inline void swap(int i, int j) { std::swap(heap[i], heap[j]); }

    inline static int u = 0, use = 0, cost = 0;

    inline void pop()
    {
        u    = heap[0][0];
        use  = heap[0][1];
        cost = heap[0][2];
        swap(0, --heapSize);
        heapify(0);
    }

    inline void heapify(int i)
    {
        int l = i * 2 + 1;
        while (l < heapSize) {
            int best = l + 1 < heapSize && heap[l + 1][2] < heap[l][2] ? l + 1 : l;
            best     = heap[best][2] < heap[i][2] ? best : i;
            if (best == i) break;
            swap(i, best);
            i = best;
            l = i * 2 + 1;
        }
    }

public:
    inline int getMinPrice(
        int city, std::vector<std::array<int, 3>>& vec, int start, int end, int k_count)
    {
        n = city;
        k = k_count;
        build();
        for (auto& v : vec) {
            addEdge(v[0], v[1], v[2]);
            addEdge(v[1], v[0], v[2]);
        }

        distance[start][0] = 0;
        push(start, 0, 0);
        while (heapSize > 0) {
            pop();
            if (visited[u][use]) continue;
            visited[u][use] = true;
            if (u == end) return cost;
            for (int ei = head[u], v, w; ei > 0; ei = next[ei]) {
                v = to[ei];
                w = weight[ei];
                if (use < k && distance[v][use + 1] > distance[u][use]) {
                    distance[v][use + 1] = distance[u][use];
                    push(v, use + 1, distance[v][use + 1]);
                }
                if (distance[v][use] > distance[u][use] + w) {
                    distance[v][use] = distance[u][use] + w;
                    push(v, use, distance[v][use]);
                }
            }
        }
        return -1;
    }
};
}   // namespace lxj

#endif